﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using System.Threading;
using System.Threading.Tasks;
using GeoAzure.Core.Threading;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Linq;
using ProtoBuf;
using ProtoBuf.Meta;
using Wintellect.Threading.ResourceLocks;
using ThreadState = System.Threading.ThreadState;

namespace GeoAzure.Core.Tests
{

    /// <summary>
    ///This is a test class for RTreeFixture and is intended
    ///to contain all RTreeFixture Unit Tests
    ///</summary>
    [TestClass()]
    public class RTreeFixture
    {
        private RTree<IBounded> _sut = new RTree<IBounded>();

        [TestMethod]
        public void EmptyIndexHasLevel1()
        {
            Assert.AreEqual(1, _sut.Level);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
        }

        [TestMethod]
        public void InsertionOfASingleElementProducesValidIndexStructure()
        {
            IBounded[] boundedObjects = TestObjectFactory.CreateBoundedObjects(1);
            _sut.InsertItem(boundedObjects[0], boundedObjects[0].Bounds);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
        }

        [TestMethod]
        public void InsertionCausesSplitOfRoot()
        {
            IBounded[] items = TestObjectFactory.CreateBoundedObjects(OverflowAlgorithm<IBounded>.MaxObjectsPerNode + 1);
            foreach (var bounded in items)
            {
                _sut.InsertItem(bounded, bounded.Bounds);
            }

            Assert.AreEqual(2, _sut.Level);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
            Assert.AreEqual(OverflowAlgorithm<IBounded>.MaxObjectsPerNode + 1, _sut.Count);
        }

        [TestMethod]
        public void InsertionOfLowNumberOfItemsDoesNotCauseSplit()
        {
            IBounded[] items = TestObjectFactory.CreateBoundedObjects(OverflowAlgorithm<IBounded>.MaxObjectsPerNode);
            foreach (var bounded in items)
            {
                _sut.InsertItem(bounded, bounded.Bounds);
            }

            Assert.AreEqual(1, _sut.Level);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
            Assert.AreEqual(OverflowAlgorithm<IBounded>.MaxObjectsPerNode, _sut.Count);
        }

        [TestMethod]
        public void InsertionChooseOptimalNode()
        {
            IBounded[] items = TestObjectFactory.CreateBoundedObjects(OverflowAlgorithm<IBounded>.MaxObjectsPerNode + 2);
            foreach (var bounded in items)
            {
                _sut.InsertItem(bounded, bounded.Bounds);
            }

            Assert.AreEqual(2, _sut.Level);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
        }

        [TestMethod]
        public void InsertionOfLargeNumberOfItems()
        {
            IBounded[] items = TestObjectFactory.CreatePointBoundedObjects(40000);
            var sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < items.Length; i++)
            {
                _sut.InsertItem(items[i], items[i].Bounds);
            }
            sw.Stop();
            var elapsed = sw.ElapsedMilliseconds;
            Console.WriteLine("inserted {0} items in {1} ms.", items.Length, elapsed);
            Console.WriteLine("Index has {0} nodes.", _sut.NodeCount);

            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
            Assert.AreEqual(items.Length, _sut.Count);
        }

        [TestMethod]
        public void DeletionOfSingleItem()
        {
            IBounded boundedObject = TestObjectFactory.CreateBoundedObjects(1)[0];
            _sut.InsertItem(boundedObject, boundedObject.Bounds);
            _sut.DeleteItem(boundedObject, boundedObject.Bounds);

            Assert.AreEqual(0, _sut.Count);
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);

        }

        [TestMethod]
        public void DeletionOfManyItemShouldCauseTreeCollapse()
        {
            IBounded[] items = TestObjectFactory.CreateBoundedObjects(OverflowAlgorithm<IBounded>.MaxObjectsPerNode + 1);
            foreach (var bounded in items)
            {
                _sut.InsertItem(bounded, bounded.Bounds);
            }

            int i = 0;
            while (_sut.Count > OverflowAlgorithm<IBounded>.MinObjectsPerNode)
            {
                IBounded bounded = items[i++];
                Assert.IsTrue(_sut.DeleteItem(bounded, bounded.Bounds));
            }

            Assert.AreEqual(1, _sut.Level); // we should have collapsed
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
        }

        [TestMethod]
        public void InsertThenDeleteThenReinsertManyItems()
        {
            const int itemCount = 40000;
            var items = InsertItems(itemCount);
            Assert.AreEqual(itemCount, _sut.Count);
            Console.WriteLine("Index has {0} nodes after initial insertion.", _sut.NodeCount);

            for (int i = 0; i < itemCount / 2; i++)
            {
                _sut.DeleteItem(items[i], items[i].Bounds);
            }
            Assert.AreEqual(itemCount / 2, _sut.Count);
            Console.WriteLine("Index has {0} nodes after deleting half the items.", _sut.NodeCount);

            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
            for (int i = 0; i < itemCount / 2; i++)
            {
                _sut.InsertItem(items[i], items[i].Bounds);
            }
            Assert.AreEqual(itemCount, _sut.Count);
            Console.WriteLine("Index has {0} nodes after reinserting items.", _sut.NodeCount);

            _sut.RootEntry.Node.AssertNodeIsValid(true, true);

        }

        private IBounded[] InsertItems(int count)
        {
            IBounded[] items = TestObjectFactory.CreatePointBoundedObjects(count);
            int min = Math.Min(count, 10000);
            for (int i = 0; i < min; i++)
            {
                _sut.InsertItem(items[i], items[i].Bounds);
            }
            if (count > 10000)
            {
                var options = new ParallelOptions() { MaxDegreeOfParallelism = 5 };
                Parallel.For(10000, items.Length, options, (i, state) => _sut.InsertItem(items[i], items[i].Bounds));
            }
            return items;
        }

        [TestMethod]
        public void DeletingEverythingShouldLeaveEmptyIndex()
        {
            IBounded[] items = InsertItems(20000);

            for (int i = 0; i < items.Length; i++)
            {
                _sut.DeleteItem(items[i], items[i].Bounds);
            }
            Assert.AreEqual(0, _sut.Count);
            Assert.AreEqual(1, _sut.NodeCount);

        }

        [TestMethod]
        public void QueryInBoundingRectangle()
        {
            IBounded[] items = InsertItems(100000);
            var queryRectangle = GeoRectangle.Create(Location.FromDegrees(10d, 0d), Location.FromDegrees(0d, 10d));
            var expectedCount = 0;
            for (int i = 0; i < items.Length; i++)
            {
                if (queryRectangle.Contains(items[i].Bounds))
                    expectedCount++;
            }

            var sw = new Stopwatch();
            sw.Start();
            IEnumerable<IBounded> queryResults = _sut.Query(queryRectangle);
            sw.Stop();
            var elapsed = sw.ElapsedMilliseconds;
            Console.WriteLine("Found {0} items among {1} in {2} ms.", queryResults.Count(), _sut.Count, elapsed);
            Assert.AreEqual(expectedCount, queryResults.Count());
            foreach (var bounded in queryResults)
            {
                Assert.IsTrue(queryRectangle.Contains(bounded.Bounds));
            }

        }

        [TestMethod]
        //[Ignore]
        public void ParallelInsertionOfLargeNumberOfItems()
        {
            IBounded[] items = TestObjectFactory.CreatePointBoundedObjects(500000);
            var sw = new Stopwatch();
            sw.Start();
            var options = new ParallelOptions() { MaxDegreeOfParallelism = 5 };
            Parallel.For(0, items.Length, options, (i, state) => _sut.InsertItem(items[i], items[i].Bounds));
            //Thread.Sleep(5000);

            sw.Stop();
            var elapsed = sw.ElapsedMilliseconds;
            Console.WriteLine("inserted {0} items in {1} ms.", items.Length, elapsed);
            Console.WriteLine("Index has {0} nodes.", _sut.NodeCount);

            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
            Assert.AreEqual(items.Length, _sut.Count);
        }

        //private Wintellect.Threading.ResourceLocks.OneManyResourceLock _lock = new OneManyResourceLock();
        //private OneManyLock _lock = new OneManyLock();
        private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);

        [TestMethod]
        public void LockTest()
        {
            const int numThreads = 3;
            Thread[] threads = new Thread[numThreads];
            for (int i = 0; i < numThreads; i++)
            {
                threads[i] = new Thread(InsertItemsCallback);
                threads[i].Start();
            }
            Thread.Sleep(5000);

            int numJoined = 0;
            for (int i = 0; i < numThreads; i++)
            {
                if (threads[i].Join(10000))
                    numJoined++;
            }
            if (numJoined == numThreads - 1)
                Thread.Sleep(1000);
            for (int i = 0; i < numThreads; i++)
            {
                Assert.IsTrue(threads[i].ThreadState == ThreadState.Stopped);
            }

            Assert.AreEqual(numThreads, numJoined);

        }

        private void InsertItemsCallback(object state)
        {
            for (int i = 0; i < 10000; i++)
            {
                bool exclusive = (i % 2 == 0);
                if (exclusive)
                    _lock.EnterWriteLock();
                else
                {
                    _lock.EnterReadLock();
                }
                Thread.Sleep(0);
                if (exclusive)
                    _lock.ExitWriteLock();
                else
                {
                    _lock.ExitReadLock();
                }
            }
        }


        [TestMethod]
        public void QueryWithinDistance()
        {
            var centerLocation = Location.FromDegrees(50d + (42.165 / 60d), 4d + (31.236 / 60d)); // my house
            const int distance = 100000; // 100km around
            IBounded[] items = InsertItems(100000);
            var expectedCount = 0;
            for (int i = 0; i < items.Length; i++)
            {
                if (centerLocation.DistanceTo(items[i].Bounds.Center) <= distance)
                    expectedCount++;
            }

            var sw = new Stopwatch();
            sw.Start();
            IEnumerable<IBounded> queryResults = _sut.QueryWithinDistance(centerLocation, distance);
            sw.Stop();
            var elapsed = sw.ElapsedMilliseconds;
            Console.WriteLine("Found {0} items among {1} in {2} ms.", queryResults.Count(), _sut.Count, elapsed);
            Assert.AreEqual(expectedCount, queryResults.Count());
            foreach (var bounded in queryResults)
            {
                Assert.IsTrue(centerLocation.DistanceTo(bounded.Bounds.Center) <= distance);
            }
        }

        [TestMethod]
        public void QueryWhileInserting()
        {
            IBounded[] items = InsertItems(100000);
            var queryRectangle = GeoRectangle.Create(Location.FromDegrees(10d, 0d), Location.FromDegrees(0d, 10d));
            var expectedCount = 0;
            for (int i = 0; i < items.Length; i++)
            {
                if (queryRectangle.Contains(items[i].Bounds))
                    expectedCount++;
            }

            items = TestObjectFactory.CreatePointBoundedObjects(100000);
            Task t = new Task(() => {
                for (int i = 0; i < items.Length; i++)
                {
                    //if (!queryRectangle.Contains(items[i].Bounds))
                        _sut.InsertItem(items[i], items[i].Bounds);
                }
            });
            t.Start();
            Thread.Sleep(1000);
            IEnumerable<IBounded> queryResults = _sut.Query(queryRectangle);
            //Assert.AreEqual(expectedCount, queryResults.Count());
            var foundCount = queryResults.Count();
            foreach (var bounded in queryResults)
            {
                Assert.IsTrue(queryRectangle.Contains(bounded.Bounds));
            }
            t.Wait();
            _sut.RootEntry.Node.AssertNodeIsValid(true, true);
        }

        [TestMethod]
        [Ignore]
        public void SerializeIndex()
        {
            IBounded[] items = TestObjectFactory.CreatePointBoundedObjects(20000);
            for (int i = 0; i < items.Length; i++)
            {
                _sut.InsertItem(items[i], items[i].Bounds);
            }

            using (Stream s = File.Open(@"D:\temp\Index.bin", FileMode.Create))
            {
                var sw = new Stopwatch();
                sw.Start();
                BinaryFormatter formatter = new BinaryFormatter();

                formatter.Serialize(s, _sut);
                Console.WriteLine("Normal serialization: elapsed {0}", sw.ElapsedMilliseconds);
            }

        }

        [TestMethod]
        [Ignore]
        public void ProtoSerialize()
        {
            RuntimeTypeModel.Default[typeof(IBounded)]
                .AddSubType(101, typeof(TreeNode<IBounded>))
                .AddSubType(102, typeof(Bounded))
                ;
            IBounded[] items = TestObjectFactory.CreatePointBoundedObjects(20000);
            for (int i = 0; i < items.Length; i++)
            {
                _sut.InsertItem(items[i], items[i].Bounds);
            }

            var b = _sut;
            using (var f = File.Create(@"D:\temp\protoser.bin"))
            {
                var sw = new Stopwatch();
                sw.Start();
                Serializer.Serialize(f, b);
                Console.WriteLine("protobuf serialization: elapsed {0}", sw.ElapsedMilliseconds);
            }

            using (var f = File.OpenRead(@"D:\temp\protoser.bin"))
            {
                var b2 = Serializer.Deserialize<RTree<IBounded>>(f);
                b2.RootEntry.Node.AssertNodeIsValid(true, true);
            }
        }
    }
}
